<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>物理时钟 - 读论文</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="favicon.svg">
        <link rel="shortcut icon" href="favicon.png">
        <link rel="stylesheet" href="css/variables.css">
        <link rel="stylesheet" href="css/general.css">
        <link rel="stylesheet" href="css/chrome.css">
        <link rel="stylesheet" href="css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="highlight.css">
        <link rel="stylesheet" href="tomorrow-night.css">
        <link rel="stylesheet" href="ayu-highlight.css">

        <!-- Custom theme stylesheets -->

        <!-- MathJax -->
        <script async type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded affix "><a href="chapter_1.html">读论文活动</a></li><li class="chapter-item expanded affix "><li class="part-title">6.824 分布式系统</li><li class="chapter-item expanded "><a href="Mapreduce.html"><strong aria-hidden="true">1.</strong> Mapreduce</a></li><li class="chapter-item expanded "><a href="GFS.html"><strong aria-hidden="true">2.</strong> GFS</a></li><li class="chapter-item expanded "><a href="VM-FT.html"><strong aria-hidden="true">3.</strong> VM-FT</a></li><li class="chapter-item expanded "><a href="Raft.html"><strong aria-hidden="true">4.</strong> Raft</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="Raft0.html"><strong aria-hidden="true">4.1.</strong> 感性认识Raft</a></li><li class="chapter-item expanded "><a href="Raft1.html"><strong aria-hidden="true">4.2.</strong> 什么是Raft？</a></li><li class="chapter-item expanded "><a href="Raft2.html"><strong aria-hidden="true">4.3.</strong> 复制状态机（Replicated State Machine）</a></li><li class="chapter-item expanded "><a href="Raft3.html"><strong aria-hidden="true">4.4.</strong> What's wrong with Paxos?</a></li><li class="chapter-item expanded "><a href="Raft4.html"><strong aria-hidden="true">4.5.</strong> 向可理解性进军</a></li><li class="chapter-item expanded "><a href="Raft5.html"><strong aria-hidden="true">4.6.</strong> Raft共识算法（零）</a></li><li class="chapter-item expanded "><a href="Raft6.html"><strong aria-hidden="true">4.7.</strong> Raft共识算法（一）——基础概念</a></li><li class="chapter-item expanded "><a href="Raft7.html"><strong aria-hidden="true">4.8.</strong> Raft共识算法（二）——选举leader</a></li><li class="chapter-item expanded "><a href="Raft8.html"><strong aria-hidden="true">4.9.</strong> Raft共识算法（三）——日志备份（log replication）</a></li><li class="chapter-item expanded "><a href="Raft9.html"><strong aria-hidden="true">4.10.</strong> Raft共识算法（四）——安全性和选举限制</a></li><li class="chapter-item expanded "><a href="Raft10.html"><strong aria-hidden="true">4.11.</strong> Raft共识算法（五）——如何提交之前term里的entry</a></li><li class="chapter-item expanded "><a href="Raft11.html"><strong aria-hidden="true">4.12.</strong> Raft共识算法（六）——安全性定理</a></li><li class="chapter-item expanded "><a href="Raft12.html"><strong aria-hidden="true">4.13.</strong> Raft共识算法（七）——如果follower/candidate宕机了</a></li><li class="chapter-item expanded "><a href="Raft13.html"><strong aria-hidden="true">4.14.</strong> Raft共识算法（八）——时间与可用性</a></li><li class="chapter-item expanded "><a href="Raft14.html"><strong aria-hidden="true">4.15.</strong> 成员变更</a></li><li class="chapter-item expanded "><a href="Raft15.html"><strong aria-hidden="true">4.16.</strong> 日志压缩</a></li><li class="chapter-item expanded "><a href="Raft16.html"><strong aria-hidden="true">4.17.</strong> 与Client的交互</a></li><li class="chapter-item expanded "><a href="Raft17.html"><strong aria-hidden="true">4.18.</strong> 实验时遇到的bug</a></li><li class="chapter-item expanded "><a href="Raft18.html"><strong aria-hidden="true">4.19.</strong> 总结</a></li></ol></li><li class="chapter-item expanded "><a href="Zookeeper.html"><strong aria-hidden="true">5.</strong> Zookeeper</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="linearizability1.html"><strong aria-hidden="true">5.1.</strong> 线性一致性（一）——基础概念</a></li><li class="chapter-item expanded "><a href="linearizability2.html"><strong aria-hidden="true">5.2.</strong> 线性一致性（二）——细究linearizability</a></li><li class="chapter-item expanded "><a href="zk_intro.html"><strong aria-hidden="true">5.3.</strong> 引言</a></li><li class="chapter-item expanded "><a href="zk_service.html"><strong aria-hidden="true">5.4.</strong> Zookeeper Service</a></li><li class="chapter-item expanded "><a href="zk_api.html"><strong aria-hidden="true">5.5.</strong> Zookeeper API</a></li><li class="chapter-item expanded "><a href="zk_prop.html"><strong aria-hidden="true">5.6.</strong> Zookeeper的性质</a></li><li class="chapter-item expanded "><a href="zk_ex.html"><strong aria-hidden="true">5.7.</strong> 基于Zookeeper实现锁</a></li></ol></li><li class="chapter-item expanded "><a href="CRAQ.html"><strong aria-hidden="true">6.</strong> CRAQ</a></li><li class="chapter-item expanded "><a href="lamport_clock.html"><strong aria-hidden="true">7.</strong> Time, Clocks, and the Ordering of Events in a Distributed System</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="lamport_clock1.html"><strong aria-hidden="true">7.1.</strong> 引言</a></li><li class="chapter-item expanded "><a href="lamport_clock_partial_order.html"><strong aria-hidden="true">7.2.</strong> 偏序关系</a></li><li class="chapter-item expanded "><a href="lamport_logic_clock.html"><strong aria-hidden="true">7.3.</strong> 逻辑时钟</a></li><li class="chapter-item expanded "><a href="lamport_total_order.html"><strong aria-hidden="true">7.4.</strong> 全序关系</a></li><li class="chapter-item expanded "><a href="lamport_clock_ana_behave.html"><strong aria-hidden="true">7.5.</strong> 异常事件</a></li><li class="chapter-item expanded "><a href="lamport_p_clock.html" class="active"><strong aria-hidden="true">7.6.</strong> 物理时钟</a></li><li class="chapter-item expanded "><a href="lamport_end.html"><strong aria-hidden="true">7.7.</strong> 结论</a></li></ol></li><li class="chapter-item expanded "><li class="part-title">6.828 操作系统</li><li class="chapter-item expanded "><a href="828intro.html"><strong aria-hidden="true">8.</strong> Killer of Microseconds</a></li><li class="chapter-item expanded "><a href="cloudlab.html"><strong aria-hidden="true">9.</strong> CloudLab</a></li><li class="chapter-item expanded "><a href="dpdk.html"><strong aria-hidden="true">10.</strong> DPDK</a></li><li class="chapter-item expanded "><a href="spdk.html"><strong aria-hidden="true">11.</strong> SPDK</a></li><li class="chapter-item expanded "><a href="Shenango.html"><strong aria-hidden="true">12.</strong> Shenango</a></li><li class="chapter-item expanded "><a href="TritonSort.html"><strong aria-hidden="true">13.</strong> TritonSort</a></li><li class="chapter-item expanded "><a href="Profiling.html"><strong aria-hidden="true">14.</strong> Profiling a warehouse-scale computer</a></li><li class="chapter-item expanded affix "><li class="part-title">6.828 - Network</li><li class="chapter-item expanded affix "><li class="part-title">CS244 - Advanced Topics in Networking</li><li class="chapter-item expanded "><a href="DARPA_NET.html"><strong aria-hidden="true">15.</strong> The Design Philosophy of The DARPA Internet Protocols</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="DARPA_NET2.html"><strong aria-hidden="true">15.1.</strong> Second Level Goals</a></li><li class="chapter-item expanded "><a href="DARPA_NET3.html"><strong aria-hidden="true">15.2.</strong> Types of Service</a></li><li class="chapter-item expanded "><a href="DARPA_NET4.html"><strong aria-hidden="true">15.3.</strong> Varieties of Networks</a></li><li class="chapter-item expanded "><a href="DARPA_NET5.html"><strong aria-hidden="true">15.4.</strong> Architecture and Implementation</a></li><li class="chapter-item expanded "><a href="DARPA_NET6.html"><strong aria-hidden="true">15.5.</strong> Datagrams</a></li></ol></li><li class="chapter-item expanded "><li class="part-title">最后</li><li class="chapter-item expanded "><a href="end.html"><strong aria-hidden="true">16.</strong> 最后</a></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">读论文</h1>

                    <div class="right-buttons">
                        <a href="print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="物理时钟"><a class="header" href="#物理时钟">物理时钟</a></h1>
<p>现在让我们把物理时钟引入到之前提到的程序时空图里。令\(C_i(t)
\)表示时钟\(C_i
\)在物理时间\(t
\)时刻的值。为了数学上方便起见，我们假设时钟是连续运行的，而非离散地&quot;ticks&quot;. (A discrete clock can be thought of as a continuous one in which there is an error of up to \(\frac{1}{2}
\) &quot;tick&quot; in reading it.)</p>
<p>更精确地，我们假设\(C_i(t)
\)是一个对时间t变量连续、可微的函数，除了时钟被重置时间的那一刻，其余时间均不会产生不连续的跳跃间断点。那么\(\frac{dC_i(t)}{dt}
\)就表示了时钟在时间\(t
\)上的变化率。</p>
<p>为了使时钟\(C_i
\)是一个真正的物理时钟，那必须尽可能地让它的变化率保证正确。即，对所有的t时刻来说，必须有\(\frac{dC_i(t)}{dt}\approx1
\)。更精确地，我们假设时钟将满足如下条件：</p>
<blockquote>
<p><strong>PC1</strong>. </p>
<p>存在一个常数\(\kappa\ll1
\)，对于所有的\(i
\)来说：\(\left| dC_i(t)/dt-1 \right|&lt;\kappa
\).
对于石英表来说，\(\kappa\leq 10^{-6}
\).</p>
</blockquote>
<p>如此，我们就有了若干独立的、能够接近正确的速率的时钟，但还不够。这些时钟之间必须能够彼此同步。即对于所有的\(i \), \(j \), \(t \)来说，要有\(C_i(t)\approx C_j(t)
\)。</p>
<p>更精确地，必须存在一个足够小的常数\(\epsilon
\)能够满足如下条件：</p>
<blockquote>
<p><strong>PC2</strong>. </p>
<p>对于所有的\(i, j
\)，都有\(\left|C_i(t)-C_j(t) \right|&lt;\epsilon
\)。</p>
</blockquote>
<p>如果把图2中程序时空图的纵轴看作是物理时间，那么PC2就说明了每一条tick line的高度误差不会超过\(\epsilon
\)。</p>
<p>由于任意两个时钟都会存在速率上的差异，它们之间时钟的读数会产生飘移，越飘越远。因此我们需要设计出一种算法，来保证条件PC2成立。不过，我们还是先看看\(\epsilon
\)和\(\kappa
\)要多小，才能保证没有异常行为的发生。</p>
<p>我们必须确保系统\(\underline{\varphi}
\)里相关的物理事件满足Strong Clock Condition。假设我们的时钟能够满足平平无奇的Clock Condition，那我们只需要考虑系统\(\underline{\varphi}
\)里任意两个并发的事件a和b也能够满足Strong Clock Condition就可以了，即系统里那些\(a\nrightarrow b
\)的事件。因此，我们只需要讨论发生在不同进程里的那些事件。</p>
<p>假设a和b属于不同进程的两个事件，并且满足\(a\rightarrow b
\)，如果事件a发生在t时刻，b发生在\(t+\mu
\)时刻。那么，\(\mu
\)就要小于进程间传递消息的最小传输时间。我们可以令\(\mu
\)等于进程之间最短距离与光速的比值。然而，\(\mu
\)取决于系统间消息传递的时间，也就是说，如果系统通信性能不佳，\(\mu
\)有可能会很大。</p>
<p>为了避免异常行为，我们必须确保对于任意的\(i, j, t
\)，都有\(C_i(t+\mu)-C_j(t)&gt;0
\)。再结合条件PC1和PC2，我们可以把\(\kappa
\)和\(\epsilon
\)的值和\(\mu
\)的值关联起来。假设当时钟重置时间的时候，它的时钟只会向前重置而不会向后重置。（如果向后重置，会导致时钟违反条件C1）</p>
<p>那么，PC1就表示\(C_i(t+\mu)-C_i(t)&gt;(1-\kappa)\mu
\)。使用PC2，如果下述不等式成立，则很容易推导出\(C_i(t+\mu)-C_j(t)&gt;0
\)：</p>
<p>$$\epsilon/(1-\kappa)\leq\mu
$$.</p>
<p>有了这个不等式，再加上PC1和PC2，那就意味着异常行为是不可能发生的。</p>
<p>现在让我们来描述我们的算法，来确保PC2一定成立。令m为物理时刻t发出的一条消息，另一个进程在\(t'
\)时刻接收到该消息。我们定义\(\nu_m=t'-t
\)为消息m的总时延。该进程在接收消息m的时候，自然不会知道这个时延的大小。不过，我们可以假设接收消息的进程知道最小时延\(\mu_m\geq0
\)即\(\mu_m\leq\nu_m
\)。我们称\(\xi_m=\nu_m-\mu_m
\)为消息的不可预测时延。</p>
<p>现在我们指明物理时钟的两个规则：
&gt;</p>
<blockquote>
<p><strong>IR1</strong>'. </p>
<p>对每个i，如果\(P_i
\)没有在物理时间t时刻接收到消息，那么\(C_i
\)在t时刻是可微的，且\(\frac{dC_i(t)}{dt}&gt;0
\)。</p>
</blockquote>
<blockquote>
<p><strong>IR2</strong>'. </p>
<p>(a) 如果\(P_i
\)在物理时刻t发送了一条消息m，那么消息m则包含了一个时间戳\(T_m=C_i(t)
\)。</p>
<p>(b)当进程\(P_j
\)在\(t'
\)时刻收到消息m的时候，进程\(P_j
\)会把\(C_j(t')
\)的值设置成\(max(C_j(t'-0), T_m+\mu_m)
\)。</p>
</blockquote>
<p>尽管上述两条规则用到了物理时间的参数，不过一个进程只需要知道它自己的时钟读数和收到消息的时间戳，就可以决定是否重置时钟了。为了数学上的方便，我们假设每个时间都发生在单个的物理时间点上，且相同的进程中，不同的事件会发生在不同的时间点上。如此，这些规则就和之前提到的IR1、IR2等价，于是该物理时钟就满足了Clock Condition。The fact that real events have a finite duration causes no difficulty in implementing the algorithm. The only real concern in the implementation is making sure that the discrete clock ticks are frequent enough so C1 is maintained.</p>
<p>现在，让我们看看这种时钟同步算法是如何满足条件PC2的。我们假设由不同进程组成的系统，可以通过一个有向图进行描述，在该有向图中，如果有从\(P_i
\)到\(P_j
\)的弧线，则表示了\(P_i
\)在给\(P_j
\)发送消息，弧长表示发送消息所需的时间。</p>
<p>我们说对于任意一个时间t来说，一条消息要经过\(\tau
\)秒才能传输完成，那么进程\(P_i
\)在t时刻发送一条消息给\(P_j
\)的话，至少\(P_j
\)到\(t+\tau
\)的时刻才能接收到。</p>
<p>The diameter of the directed graph is the smallest number \(d
\) such that for any pair of distinct processes \(P_j, P_k
\)there is a path from \(P_j
\)to\(P_k
\) having at most \(d
\)arcs.</p>
<p>为了使PC2成立，下述定理限制了系统启动后，时钟同步所需要的时间。</p>
<p>定理：
假设具有半径d的进程有向图总是满足规则IR' 和 IR2'。 对于任何一个消息m，\(\mu_m\leq\mu
\)对于某些常数\(\mu
\)成立，并且当\(t\geq t_0
\)时，(a) PC1成立。(b) 存在常数\(\tau
\)和\(\xi
\)，每隔\(\tau
\)秒后，一个具有小于\(\xi
\)的不可预测时延的消息m会在每个弧线上发出。
当\(t\geq t_0+\tau d
\)时，有\(\epsilon\approx d(2\kappa\tau+\xi)
\)，近似地可以看作\(\mu+\xi\ll\tau
\)，于是PC2满足。</p>
<p>这个定理的证明相当困难，我们在附录里给出了证明。学术界有很多工作致力于解决物理时钟同步的问题。我们推荐读者去读《Ellingson, C, and Kulpinski, R.J. Dissemination of system-time. 1973》。文献中描述了一种估计消息传递延时，并且校准时钟频率的方法。However, the requirement that clocks are never set backwards seems to distinguish our situation from ones previously studied, and we believe this theorem to be a new result.</p>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="lamport_clock_ana_behave.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="lamport_end.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="lamport_clock_ana_behave.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="lamport_end.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
